package leetcode_200;

import java.util.HashMap;
import java.util.Map;

/**
 *@author 周杨
 *FractionToRecurringDecimal_166_ 给定一个分子和分母 求他们相除结果的字符串 循环用括号括起来
 *describe:用hashMap保存每次的除数  如果有出现过的 则把其下标对应的数字扩起来
 *		   1.注意正负号关系  若Integer.MIN_VALUE转正数 则溢出
 *AC 80%
 *2018年6月8日 上午10:47:43
 */
public class FractionToRecurringDecimal_166_ {

	public static void main(String[] args) {
		FractionToRecurringDecimal_166_ test=new FractionToRecurringDecimal_166_();
		/*System.out.println(test.fractionToDecimal(20, 3));
		System.out.println(test.fractionToDecimal(1, 2));
		System.out.println(test.fractionToDecimal(2, 1));*/
		System.out.println(test.fractionToDecimal(4, 333));

	}
	
	
	/*public String fractionToDecimal(int numerator, int denominator) {
        StringBuilder res=new StringBuilder();
        int pre=numerator%denominator;
        int after=numerator/denominator;
        res.append(after);
        if(pre!=0)
        	res.append(".");
        while(pre!=0) {
        	int now=pre*10%denominator;
        	if(now==pre) {
        		res.append("(").append(pre*10/denominator)
        		.append(")");
        		break;
        	}
        	res.append(pre*10/denominator);
        	pre=now;
        }
        
        return res.toString();
    }*/
	
	public String fractionToDecimal(int numerator, int denominator) {  
        if (numerator == 0) return "0";  
        if (denominator == 0) return "";  
          
        String ans = "";  
          
        //如果结果为负数  
        if ((numerator < 0) ^ (denominator < 0)) {  
            ans += "-";  
        }  
          
        //下面要把两个数都转为正数，为避免溢出，int转为long  
        long num = numerator, den = denominator;  
        num = Math.abs(num);  
        den = Math.abs(den);  
          
        //结果的整数部分  
        long res = num / den;  
        ans += String.valueOf(res);  
          
        //如果能够整除，返回结果  
        long rem = (num % den) * 10;  
        if (rem == 0) return ans;  
          
        //结果的小数部分  
        HashMap<Long, Integer> map = new HashMap<Long, Integer>();  
        ans += ".";  
        while (rem != 0) {  
            //如果前面已经出现过该余数，那么将会开始循环  
            if (map.containsKey(rem)) {  
                int beg = map.get(rem); //循环体开始的位置  
                String part1 = ans.substring(0, beg);  
                String part2 = ans.substring(beg, ans.length());  
                ans = part1 + "(" + part2 + ")";  
                return ans;  
            }  
              
            //继续往下除  
            map.put(rem, ans.length());  
            res = rem / den;  
            ans += String.valueOf(res);  
            rem = (rem % den) * 10;  
        }  
          
        return ans;  
    }  

}
